class Solution
{
public:
    // 开辟一个数组预存尾部字符的最小值，使得时间复杂度降到 n
    string robotWithString(string s)
    {
        int n = s.size();
        vector<char> tailMin(n);
        tailMin[n - 1] = s[n - 1];
        for (int i = n - 2; i >= 0; --i)
        {
            tailMin[i] = min(s[i], tailMin[i + 1]);
        }
        stack<char> st;
        int i = 0;
        int last = 0;
        string result;
        while (i < n)
        {
            if (s[i] == tailMin[i])
            {
                while (!st.empty() && st.top() <= s[i])
                {
                    result += st.top();
                    st.pop();
                }
                for (int prev = last; prev < i; ++prev)
                {
                    st.push(s[prev]);
                }
                result += s[i];
                last = ++i;
            }
            else
            {
                ++i;
            }
        }
        while (!st.empty())
        {
            result += st.top();
            st.pop();
        }
        return result;
    }

    // 最坏情况下时间复杂度 n^2, 超时
    string robotWithString(string s)
    {
        stack<char> st;
        auto last = s.begin();
        string result;
        while (last != s.end())
        {
            auto cur = min_element(last, s.end());
            while (!st.empty() && st.top() <= *cur)
            {
                result += st.top();
                st.pop();
            }
            for (auto it = last; it != cur; ++it)
            {
                st.push(*it);
            }
            result += *cur;
            last = ++cur;
        }
        while (!st.empty())
        {
            result += st.top();
            st.pop();
        }
        return result;
    }
};